#shellsort.S


#include <mips/regdef.h>

#FUNCION AUXILIAR STRCMP
#int strcmp2(char* c1, char* c2)

.text
.ent strcmp2
.align 2

strcmp2:
	subu sp,sp,8	#Stack de 8b
	sw $fp,4(sp)
	sw gp,0(sp)
	move $fp,sp

	sw a0, 8(sp)	#En el stack del caller, 8(sp)= argumento 0 (cadena1)
	sw a1, 12(sp)	#En el stack del caller, 12(sp)= argumento 1 (cadena2)

	li t5,0		#Guarda 0 en t5
	# c1= cadena1
	# c2= cadena2
	move t1,a0	#c1 en t1
	move t2,a1	#c2 en t2
	# ch1= caracter de cadena1
	# ch2= caracter de cadena2
	lbu t6,0(t1)	#en t6 esta ch1
	lbu t7,0(t2)	#en t7 esta ch2

loopstrcmp:	
	beq t6,zero,ch1escero		#¿ch1 es cero?
	beq t7,zero,ch2escero		#¿ch2 es cero?
					#Si llego aca, ni ch1 ni ch2 son cero.
	sub t4,t6,t7			#t4=t6-t7
	bltz t4,devolvermenosuno	#si ch1-ch2<0, ch2>ch1
	bgtz t4,devolveruno		#si ch1>ch2
	li t4,1				#Guarda 1 en t4
	add t1,t1,t4
	add t2,t2,t4
	lbu t6,0(t1)			#en t6 esta ch1
	lbu t7,0(t2)			#en t7 esta ch2
	b loopstrcmp

ch1escero:	beq t7,zero,devolvercero	#¿ch2 es cero?
		b devolvermenosuno		#ch1 es cero, pero ch2 no. Devolver 1.

ch2escero:	b devolveruno


devolveruno:	li v0,1			#valor de retorno 1
		b fin

devolvermenosuno:	li v0,-1	#valor de retorno -1
			b fin

devolvercero:	move v0,zero		#valor de retorno 0
		b fin

fin:		#Desarmar stack
		lw $fp,4(sp)
		lw gp,0(sp)	
		addiu sp,sp,8
		jr ra

.end strcmp2


#FUNCION AUXILIAR INSERTION SORT PARCIAL
# void insertionSortParcial(char** words, int arraysize, int inicio, int gap)

.text
.ent insertionsortParcial
.align 2

#define wsize 4

insertionsortParcial:

	subu sp,sp,48			#Stack de 48b
	sw $fp,36(sp)
	sw gp,32(sp)
	sw ra,40(sp)
	move $fp,sp

	sw a0, 48(sp)	#En el stack del caller, 48(sp)= argumento 0 (**words)
	sw a1, 52(sp)	#En el stack del caller, 52(sp)= argumento 1 (arraysize)
	sw a2, 56(sp)	#En el stack del caller, 56(sp)= argumento 2 (inicio)
	sw a3, 60(sp)	#En el stack del caller, 60(sp)= argumento 3 (gap)

	move t0,a0				#t0 = char **words
	move t1,a1				#t1 = arraysize
	move t2,a2				#t2 = i = inicio
	move t3,a3				#t3 = gap
loopi1:
	bge t2,t1,fini			#inicio >= arraysize
	move t4,t2				#j = i
	add t2,t2,t3			#i += gap
loopi2:
	sub t5,t4,t3			#t5 = j-gap
	bltz t5,loopi1			#if j-gap < 0, salimos del for
	li t6,wsize
	mul t6,t4,t6			#t6 = j*4
	add t6,t0,t6			#t6 = **words + 4*j
	lw t6,0(t6)			#t6 = words[j]
	li t7,wsize
	mul t7,t5,t7			#t7 = (j-gap)*4
	add t7,t0,t7			#t7 = **words + 4*(j-gap)
	lw t7,0(t7)			#t7 = words[j-gap]
		#me preparo para el salto de funcion
	move a0,t6
	move a1,t7
	sw t6,16(sp)			#words[j-gap]
	sw t7,20(sp)			#words[j]
	sw t2,28(sp)			#guardo i
	sw t4,24(sp)			#guardo j
	jal strcmp
	#Guardo datos en registros temporales
	lw t0,48(sp)			# **words
	lw t1,52(sp)			# arraysize
	lw t2,28(sp)			# i
	lw t3,60(sp)			# gap
	lw t4,24(sp)			# j

	sub t5,t4,t3			#t5 = j-gap
		#continuo
	bgtz v0,loopi1 			#si la comparacion dio >= 0 salgo
	li t7,wsize
	mul t7,t4,t7			#t7 = j*4
	add t7,t0,t7			#t7 = **words + 4*j
	lw t6,20(sp)			#t6 = word[j]
	sw t6,0(t7)			#guardo [i-j] donde estaba [j]
	li t7,wsize
	mul t7,t5,t7			#t7 = (j-gap)*4
	add t7,t0,t7			#t7 = **words + 4*(j-gap)
	lw t6,16(sp)			#t6 = word[i-j]
	sw t6,0(t7)				#guardo [j] donde estaba [j-gap]
	sub t4,t4,t3			#j-=gap
	j loopi2
fini:
	lw ra,40(sp)	#Desarmo el stack
	lw gp,32(sp)
	lw $fp,36(sp)
	addu sp,sp,48
	jr ra

.end insertionsortParcial

#FUNCION PRINCIPAL SHELLSORT
# void shellsort(char** words, int arraysize)

.globl shellsort2
.ent shellsort2
.align 2

shellsort2:
	subu sp,sp,32		#Stack de 32b
	sw ra,24(sp)
	sw $fp,20(sp)
	sw gp,16(sp)
	move $fp,sp
	# sw a0, 32(sp)	#En el stack del caller, 32(sp)= argumento 0 (**words)
	# sw a1, 36(sp)	#En el stack del caller, 36(sp)= argumento 1 (arraysize)
	move t0,a0			#t0 = **words
	move t1,a1			#t1 = arraysize
	li t2,1			#t2 = gap
loopgap:
	bgt t2,t1,loopsort	#if (gap > arraysize) break;
	li t3,3			#t3 = 3
	mul t2,t2,t3		#gap = gap * 3
	addi t2,t2,1		#gap = gap + 1
	j loopgap
loopsort:
	blez t2,finss		#gap <= 0, termine
	li t3,3			#t3 = 3
	div t2,t2,t3		#gap = gap/3		
					#for i=0; i < gap; i++
	li t4,0			#t4 = i = 0
for:
	bge t4,t2,loopsort	#while i <= gap ejecuto for
		#Me preparo para llamar la funcion de parametros (char** words, int arraysiz, int inicio, int gap)
	move a0,t0			#Guardo params en regs
	move a1,t1
	move a2,t4
	move a3,t2
	jal insertionsortParcial
	#Vuelvo a cargar los valores (que eran los que pase por parametro)
	lw t0,0(sp)			#t0 = **words
	lw t1,4(sp)			#t1 = arraysize
	lw t4,8(sp)			#t4 = i
	lw t2,12(sp)		#t2 = gap	
		#Fin de la llamada
	addi t4,t4,1		#++i
	j for
finss:				#Desarmar stack
	lw ra,24(sp)
	lw $fp,20(sp)
	lw gp,16(sp)	
	addiu sp,sp,32
	jr ra	

.end shellsort2

